package 剑指offer.树;

/**
 * 给出一颗二叉树以及一个节点，如何找出中序遍历的下一个节点？
 *
 * 此二叉树还有指向父节点的指针
 */
public class 第8题二叉树的下一个节点 {

    static class TreeNode {
        String val;
        TreeNode left;
        TreeNode right;
        TreeNode parent;

        public TreeNode(String val) {
            this.val = val;
        }
    }

    /**
     * 处理思路：先要确定待处理节点的类型：
     *  若是一个含有子节点的节点，答案就是该节点的右孩子里面的最左子节点
     *  若是一个子节点，则还要考虑它是左孩子还是右孩子：
     *      若是左孩子：下一个节点就是该左孩子的 parent
     *      若是右孩子：则需要回溯至根节点，回溯到自己不是某一个节点的右孩子即可，此时下一个节点就是当前的 parent
     */
    public static TreeNode getNextNode(TreeNode head) {
        if (head == null) {
            return null;
        }
        TreeNode ans = null;
        // 如果当前的节点是一个含有子节点的节点，那么他的下一个节点就是一直往右遍历的最左子节点
        if (head.right != null) {
            TreeNode temp = head.right;
            while (temp.left != null) {
                temp = temp.left;
            }
            ans = temp;
        }
        // 如果当前节点是叶子节点，又分为左叶子和右叶子
        else if (head.parent != null) {
            TreeNode curr = head;
            TreeNode parent = curr.parent;
            // 若是右叶子节点，下一个节点需要往回溯，直到找到一个节点，他的父节点的左子树就是他。那么ans就是该节点的父节点
            while (parent != null && curr == parent.right) {
                curr = parent;
                parent = curr.parent;
            }
            // 遍历完后，curr 的位置很巧妙，它处于左叶子节点的位置，不管上面是否执行行了遍历
            // 还是说当前节点就是一个左结点，下一个节点都是该节点的父节点！
            ans = parent;
        } else {
            System.out.println("只有根节点，不存在下一个节点，下一个节点就是 null");
        }
        return ans;
    }

    public static void main(String[] args) {
        TreeNode a = new TreeNode("a");
        TreeNode b = new TreeNode("b");
        TreeNode d = new TreeNode("d");
        TreeNode e = new TreeNode("e");
        TreeNode c = new TreeNode("c");

        a.left = b;
        a.right = c;
        c.parent = a;

        b.left = d;
        b.right = e;
        b.parent = a;

        d.parent = b;
        e.parent = b;

        TreeNode ans = getNextNode(d);
        System.out.println(ans.val);
    }
}
